package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC373 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 本次思路参考了合并k个有序链表
     * 其实也可以用丑数的思路，丑数这块还需要复习一下
     * @return:
     */
    class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            // 小顶堆
            PriorityQueue<int[]> queue = new PriorityQueue<>(
                    (o1, o2) -> (nums1[o1[0]] + nums2[o1[1]]) - (nums1[o2[0]] + nums2[o2[1]]));
            List<List<Integer>> res = new LinkedList<>();

            // 两个数组有一个为空，返回空
            if (nums1.length == 0 || nums2.length == 0) {
                return res;
            }

            // 将我们假想的每个数组的第一项加入小顶堆
            for (int i = 0; i < Math.min(nums1.length, k); i++) {
                queue.add(new int[]{i, 0}); // 加入的是坐标，小顶堆的比较器也是基于坐标比较
            }

            // 循环K次或者堆空
            while (k > 0 && !queue.isEmpty()) {
                // 弹出堆顶元素
                int[] pair = queue.poll();
                List<Integer> item = new ArrayList<>();
                item.add(nums1[pair[0]]);
                item.add(nums2[pair[1]]);

                // 若我们假想的数组有下一个元素，则加入小顶堆
                if (pair[1] < nums2.length - 1) {
                    queue.add(new int[]{pair[0], pair[1] + 1});
                }
                res.add(item);
                k--;
            }
            return res;
        }
    }


    //    输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
//    输出: [1,2],[1,4],[1,6]
    public void run() {
        Solution solution = new Solution();
        int[] arr1 = InputUtil.toIntegerArray("[1,7,11]");
        int[] arr2 = InputUtil.toIntegerArray("[2,4,6]");
        System.out.println(solution.kSmallestPairs(arr1, arr2, 3));
    }

    public static void main(String[] args) throws Exception {
        LC373 an = new LC373();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
